package 模拟;

import java.util.HashMap;
import java.util.Map;

//思路： 可以利用哈希表来进行判断，
// 首先每遍历一个的字符串都要进行判断，最后 k 来代表最终完整一次
// r,o,a,k 时都要判断前驱字符是否存在，如果存在，前驱个数--，当前字符++ 不存在，返回-1
// c ,找最后一个字符，
// 如果在哈希表里存在，最后一个字符--（把叫完的青蛙剥离让他重新叫这个，可以使所需青蛙个数最小），当前字符++（// 因为要返回字符串所有蛙鸣，所需青蛙的最小个数）
// 不存在当前字符++

// 如果不存在，就再遍历下一个字符串。直到 遍历到k算为一个完整
// 因为要返回字符串所有蛙鸣，所需青蛙的最小个数
public class 数青蛙1419 {

    public int minNumberOfFrogs(String c) {
        char[] croakOfFrogs = c.toCharArray();//把字符串数组化
        String t = "croak"; //完整命令
        int n = t.length();
        int[] hash = new int[n]; // 数组模拟哈希表

        Map<Character, Integer> index = new HashMap<>();//{x,与x这个字符对应的下标}

        for (int i = 0; i < n; i++)
            index.put(t.charAt(i), i); //将成功字符先存入
        for (char ch : croakOfFrogs) //开始遍历提供的字符
        {
            if (ch == t.charAt(0))  //当遇到第一个开头时
            {
                if (hash[n - 1] != 0) hash[n - 1]--; //如果已经完成过一次字符遍历，便利次数-1？
                hash[0]++; // 进入筛选流程
            } else {
                int i = index.get(ch);
                if (hash[i - 1] == 0) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }

        for (int i = 0; i < n - 1; i++)
            if (hash[i] != 0)
                return -1;
        return hash[n - 1];
    }

}
